#include <iostream>
#include <unordered_map>
#include <vector>
#include <iomanip>

using namespace std;

struct Node
{
    int address; // 节点地址
    int key;     // 节点值
    int next;    // 下一个节点地址
};

int main()
{
    int headAddr, N;
    cin >> setw(5) >> headAddr >> N;

    unordered_map<int, Node> nodes; // 存储链表节点
    vector<Node> resultList;        // 存储去重后的链表
    vector<Node> deletedList;       // 存储被删除的链表
    unordered_map<int, bool> seen;  // 记录绝对值是否已出现

    // 读取链表节点信息
    for (int i = 0; i < N; ++i)
    {
        Node node;
        cin >> node.address >> node.key >> node.next;
        nodes[node.address] = node; // 将节点信息存入哈希表
    }

    int currentAddr = headAddr; // 从头节点开始遍历链表

    // 遍历链表
    while (currentAddr != -1)
    {
        Node currentNode = nodes[currentAddr]; // 获取当前节点
        int absKey = abs(currentNode.key);     // 计算当前节点值的绝对值

        if (seen[absKey])
        {
            // 该绝对值已出现，放入被删除的链表
            deletedList.push_back(currentNode);
        }
        else
        {
            // 第一次出现，放入去重后的链表
            if (!resultList.empty())
            {
                resultList.back().next = currentNode.address;
                // 正确连接列表
            }
            resultList.push_back(currentNode);
            seen[absKey] = true; // 标记该绝对值已出现
        }

        // 移动到下一个节点
        currentAddr = currentNode.next;
    }

    // 确保最后一个节点的 next 为 -1
    if (!resultList.empty())
    {
        resultList.back().next = -1;
    }

    // 输出去重后的链表
    for (const auto &node : resultList)
    {
        if (node.next == -1)
        {
            cout << setw(5) << setfill('0') << node.address << " "
                 << node.key << " "
                 //<< setw(5) << setfill('0') < <
                 << node.next << endl;
        }
        else
        {
            cout << setw(5) << setfill('0') << node.address << " "
                 << node.key << " "
                 << setw(5) << setfill('0') << node.next << endl;
        }
    }

    // 输出被删除的链表
    for (const auto &node : deletedList)
    {
        if (node.next == -1)
        {
            cout << setw(5) << setfill('0') << node.address << " "
                 << node.key << " "
                 //<< setw(5) << setfill('0') < <
                 << node.next << endl;
        }
        else
        {
            cout << setw(5) << setfill('0') << node.address << " "
                 << node.key << " "
                 << setw(5) << setfill('0') << node.next << endl;
        }
    }

    return 0;
}
/*#include <iostream>
#include <unordered_map>
#include <vector>
#include <iomanip>

using namespace std;

struct Node
{
    int address; // 节点地址
    int key;     // 节点值
    int next;    // 下一个节点地址
};

int main()
{
    int headAddr, N;
    cin >> setw(5) >> headAddr >> N;

    unordered_map<int, Node> nodes; // 存储链表节点
    vector<Node> resultList;        // 存储去重后的链表
    vector<Node> deletedList;       // 存储被删除的链表
    unordered_map<int, bool> seen;  // 记录绝对值是否已出现

    // 读取链表节点信息
    for (int i = 0; i < N; ++i)
    {
        Node node;
        cin >> node.address >> node.key >> node.next;
        nodes[node.address] = node; // 将节点信息存入哈希表
    }

    int currentAddr = headAddr; // 从头节点开始遍历链表

    // 遍历链表
    while (currentAddr != -1)
    {
        Node currentNode = nodes[currentAddr]; // 获取当前节点
        int absKey = abs(currentNode.key);     // 计算当前节点值的绝对值

        if (seen[absKey])
        {
            // 该绝对值已出现，放入被删除的链表
            deletedList.push_back(currentNode);
        }
        else
        {
            // 第一次出现，放入去重后的链表
            if (!resultList.empty())
            {
                resultList.back().next = currentNode.address; // **正确连接上一个节点到当前节点**
            }
            resultList.push_back(currentNode);
            seen[absKey] = true; // 标记该绝对值已出现
        }

        // 移动到下一个节点
        currentAddr = currentNode.next;
    }

    // 确保最后一个节点的 next 为 -1
    if (!resultList.empty())
    {
        resultList.back().next = -1; // **确保最后节点的指向为-1**
    }

    // 输出去重后的链表
    for (const auto &node : resultList)
    {
        cout << setw(5) << setfill('0') << node.address << " "
             << node.key << " "
             << setw(5) << setfill('0') << node.next << endl; // **确保输出格式统一**
    }

    // 输出被删除的链表
    for (const auto &node : deletedList)
    {
        cout << setw(5) << setfill('0') << node.address << " "
             << node.key << " "
             << setw(5) << setfill('0') << node.next << endl; // **确保输出格式统一**
    }

    return 0;
}*/